using System;

public class SparseArray<T>
{
    T[] _array;
    int[] _freeIndexArray;
    int _maxCount;
    int _freeCount;

    public int Count { get => _maxCount - _freeCount; }
    public int MaxCount { get => _maxCount; }
    public T this[int index]
    {
        get { return _array[index]; }
        set { _array[index] = value;}
    }

    public SparseArray(int capacity)
    {
        capacity = capacity >= 4 ? capacity : 4;
        _array = new T[capacity];
        _maxCount = 0;
        _freeCount = 0;
        _freeIndexArray = new int[capacity];
    }

    public void Clear()
    {
        _maxCount = 0;
        _freeCount = 0;
    }

    // 返回添加元素所在的index
    public int Add(T item)
    {
        if (_freeCount > 0) //插入在空白处
        {
            int index = _freeIndexArray[--_freeCount];
            _array[index] = item;
            return index;
        }
        else // 放在最后
        {
            if (_maxCount == _array.Length)
            {
                Resize();
            }
            int index = _maxCount++;
            _array[index] = item;
            return index;
        }
    }
    public void RemoveAt(int index)
    {
        _array[index] = default;
        _freeIndexArray[_freeCount++] = index;
    }

    void Resize()
    {
        Resize(2 * _array.Length);
    }
    void Resize(int newCapacity)
    {
        if (newCapacity > _array.Length)
        {
            Array.Resize(ref _array, newCapacity);
            Array.Resize(ref _freeIndexArray, newCapacity);
        }
    }
}
